package a10_动态规划;

import java.util.Arrays;

/**
 * <p>
 * a47_判断子序列复习2
 * </p>
 *
 * @author flyduck
 * @since 2025/3/24
 */
public class a47_判断子序列复习2 {

    public static void main(String[] args) {
        System.out.println(isSubsequence("abc", "ahbgdc"));
    }
    //也就是s和t的公共子序列是s.length

    //dp[i][j]：chars1[0~i-1]和chars2[0~j-1]的最长公共子序列是dp[i][j]

    //递推公式：
    //if(chars1[i-1] == chars[j-1]){
    //  dp[i][j] = dp[i-1][j-1] + 1
    //}else{
    //   ABCD
    //  ABCDE
    //  ABC和ABCD的最长公共子序列是3
    //  D和E不一样
    //  D有可能和ABCDE的某个相等
    //  E有可能和ABCD的某个相等（相当于我们跳过D了，因为我们求得是s是t的子序列，所以不能跳过s的任何元素）
    //  dp[i][j] = dp[i][j-1]
    //}

    public static boolean isSubsequence(String s, String t) {
        char[] chars1 = s.toCharArray();
        char[] chars2 = t.toCharArray();

        int[][] dp = new int[chars1.length+1][chars2.length+1];

        for (int i = 1; i <= chars1.length; i++) {
            for (int j = 1; j <= chars2.length; j++) {
                if(chars1[i-1] == chars2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    dp[i][j] = dp[i][j-1];
                }
            }
            System.out.println(Arrays.toString(dp[i]));
        }

        return dp[chars1.length][chars2.length] == chars1.length;
    }
}
